1. Field of the Invention
The present invention generally relates to a signal processing apparatus and a signal processing method. More particularly, the invention relates to a signal processing apparatus and a signal processing method which are heavily used in, for example, fast FOURIER transform.
2. Description of the Related Art
Fast FOURIER transform (FFT) used in, for example, Digital Video Broadcasting-Terrestrial (DVB-T), is implemented by repeating complex calculations, which are referred to as "butterfly calculations".
In butterfly calculations, the number of data items that are calculated simultaneously varies according to the number, which is referred to as the "cardinal number". The number of repetitions of the butterfly calculations at one time in FFT is also determined by the cardinal number.
Generally, for various reasons of convenience (for example, the simplicity of the construction), a butterfly calculating circuit system having a cardinal number of four is frequently used. However, if the number of data to be subjected to FFT calculations (which is referred to as "the point number of FFT") is other than four to the power of n, FFT cannot be performed using only the butterfly calculations of a cardinal number of four.
In this case, it is necessary to add butterfly calculations of a cardinal number of two to a butterfly calculating circuit system having a cardinal number of four. Accordingly, in terms of the configuration of the circuitry, the addition of a butterfly calculating circuit system having a cardinal number of two is required.
FIGS. 5A and 5B respectively illustrate an example of a known butterfly calculating circuit system having a cardinal number of four and an example of a conventional butterfly calculating circuit system having a cardinal number of two.
The butterfly calculating circuit system having a cardinal number of four shown in FIG. 5A is formed of complex multiplication circuits 1 through 3 and complex addition circuits 4 through 7. The signal lines connecting the black dots on the left side of FIG. 5A and the complex addition circuits 4 through 7 on the right side of FIG. 5A are used to multiply input complex data by 1, -1, j, and -j and to output the multiplied data. Input data IA0 through IA3 indicate complex data. IB1 through IB3 indicate complex constant data, which is, for example, stored in a ROM, read, and supplied.
The operation of the above-described known butterfly calculating circuit system is as follows.
The complex multiplication circuits 1 through 3 multiply IA1 by IB1, IA2 by IB2, and IA3 by IB3, respectively, and output the multiplied data.
The input data IA0 is input into the complex addition circuits 4 and 5. An output of the complex multiplication circuit 1 is multiplied by 1, -j, 1, and j, and the multiplied values are respectively input into the complex addition circuits 4 through 7. An output of the complex multiplication circuit 2 is multiplied by 1, -1, 1, and -1, and the multiplied values are respectively input into the complex addition circuits 4 through 7. An output of the complex multiplication circuit 3 is multiplied by 1, j, -1, and -j, and the multiplied values are respectively input into the complex addition circuits 4 through 7.
The complex addition circuits 4 through 7 add the input data IA0 to the outputs of the complex multiplication circuits 1 through 3 multiplied by constants (1, -1, J, and -j) and output the added values as O0 through O3, respectively.
According to the above-described circuit system, butterfly calculations of a cardinal number of four can be performed.
An example of the configuration of a butterfly calculating circuit system having a cardinal number of two is described below with reference to FIG. 5B.
The butterfly calculating circuit system is formed, as shown in FIG. 5B, of a complex multiplication circuit 8 and complex addition circuits 9 and 10. IA0 and IA1 indicate input data, and IB1 represents constant data stored in, for example, a ROM.
The operation of the above example is as follows.
The input data IA0 is input into the complex addition circuits 9 and 10. The input data IA1 and the constant data IB1 are input into the complex multiplication circuit 8 in which the data IA1 and IB1 are complex-multiplied. The multiplied data is then supplied to the complex addition circuit 9, and is also supplied to the complex addition circuit 10 after being multiplied by -1.
The complex addition circuit 9 adds the input data IA0 to the output of the complex multiplication circuit 8 and outputs the resulting data as O0. Moreover, the complex addition circuit 10 adds the input data IA0 to the output of the complex multiplication circuit 8 multiplied by -1 and outputs the resulting data as O1.
According to the foregoing configuration of the circuit system, butterfly calculations of a cardinal number of two can be performed.
When the point number is other than four to the power of n, it is necessary to form FFT circuitry by using both the butterfly calculating circuit system having a cardinal number of four and the butterfly calculating circuit system having a cardinal number of two. This enlarges the resulting circuitry by an amount equal to a butterfly calculating circuit system having a cardinal number of two (which is the circuit system shown in FIG. 5B) over FFT circuitry whose point number is four to the power of n. Moreover, a butterfly calculating circuit system having a cardinal number of two is used only in part of the FFT processing, and it is thus burdensome to separately form a circuit system, which is not frequently used.